package xjggb.algorithm.排序.sort.merge;

import xjggb.algorithm.排序.sort.Sort;

public class Merge <T extends Comparable<T>> extends Sort<T> {
    private T[] leftArray;
    @Override
    protected void sort() {
        leftArray = (T[]) new Comparable[array.length >> 1];
        sort(0, array.length);
    }
    protected void sort(int begin,int end) {
        //至少要有两个元素
        if (end-begin<2)return;
        //对半切分
        int mid=(begin+end)>>1;
        sort(begin,mid);
        sort(mid,end);
        merge(begin,mid,end);
    }

    /*
    * 将 [begin, mid) 和 [mid, end) 范围的序列合并成一个有序序列
    * */
    private void merge(int begin, int mid, int end) {
        int li =0 , le = mid-begin; //li表示临时数组得初始变量， le表示临时数组得长度
        int ri=mid, re=end;     //右边数组得长度
        int ai=begin;           //右边得索引起始值

        //拷贝左边数组到leftArray
        for (int i = 0; i <le ; i++) {
            leftArray[i]=array[begin+i];
        }
        while (li<le){
            if (ri<re&&cmp(array[ri],leftArray[li])<0){
                array[ai++]=array[ri++];  //拷贝右边数组
            }else {
                array[ai++]=leftArray[li++];
            }
        }
    }




}
